<算法>一些排序算法

效率比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//---------------------------------------------------------------
//| 排序算法 | 平均情况         | 最好情况   | 最坏情况   | 稳定性 |
//---------------------------------------------------------------
//| 冒泡排序 |  O(n²)          |  O(n)     |  O(n²)    | 稳定   |
//---------------------------------------------------------------
//| 选择排序 |  O(n²)          |  O(n²)    |  O(n²)    | 不稳定 |
//---------------------------------------------------------------
//| 插入排序 |  O(n²)          |  O(n)     |  O(n²)    | 稳定   |
//---------------------------------------------------------------
//| 希尔排序 |  O(nlogn)~O(n²) |  O(n^1.5) |  O(n²)    | 不稳定 |
//---------------------------------------------------------------
//| 归并排序 |  O(nlogn)       |  O(nlogn) |  O(nlogn) | 稳定   |
//---------------------------------------------------------------
//| 快速排序 |  O(nlogn)       |  O(nlogn) |  O(n²)    | 不稳定 |
//---------------------------------------------------------------

冒泡排序

  • 步骤
  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
  • 小到大排序：大的向上冒泡移动
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function bableSort(arr = []) {
  const len = arr.length;
  if (len < 2) {
    return arr;
  }
  for (let i = len - 1; i > 0; i--) {
    let change = false;
    for (let j = 0; j < i; j++) {
      let a = arr[j];
      let b = arr[j + 1];
      if (a > b) {
        arr[j] = b;
        arr[j + 1] = a;
        change = true;
      }
    }
    // 如果没有交换，不需要继续处理
    if (!change) {
      break;
    }
  }
  return arr;
}

选择排序

  • 步骤
  1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
  2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
  3. 重复第二步，直到所有元素均排序完毕。
  • 小到大排序：从首位开始，依次找到剩余最小的交换
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function selectSort(arr = []) {
  const len = arr.length;
  if (len < 2) {
    return arr;
  }
  for (let i = 0; i < len; i++) {
    const temp = arr[i];
    let minIndex = i;
    for (let j = i + 1; j < len; j++) {
      if (arr[minIndex] > arr[j]) {
        minIndex = j;
      }
    }
    if (i !== minIndex) {
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
    }
  }
  return arr;
}

插入排序

  • 步骤
  1. 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
  2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
  • 小到大排序：从第二位开始，缓存当前值，向前寻找，如果值比缓存值大，移动位置，最后插入合适位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function insertSort(arr) {
  let len = arr.length;
  if (len < 2) {
    return arr;
  }
  for (let i = 1; i < len; i++) {
    let j = i;
    const temp = arr[i];
    while (j > 0 && arr[j - 1] > temp) {
      //寻找第 i 项应该插入位置
      arr[j] = arr[j - 1]; // 移动数据，空出位置
      j--;
    }
    arr[j] = temp;
  }
  return arr;
}

快速排序

  • 步骤
  1. 从数列中挑出一个元素，称为 “基准”（pivot）
  2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作
  3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function quickSort(arr = []) {
  const len = arr.length;
  if (len < 2) {
    return [];
  }
  // 找基准
  const index = Math.floor(len / 2);
  const indexVal = arr.splice(index, 1)[0]; // 原数组排除基准
  const left = [];
  const right = [];
  for (let d of arr) {
    if (d < indexVal) {
      left.push(d);
    } else {
      right.push(d);
    }
  }
  //递归调用，并拼接数组
  return quickSort(left).concat(indexVal).concat(right);
}
  • 三路快排：添加等于基准的数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function quickSort(arr = []) {
  const len = arr.length;
  if (len < 2) {
    return [];
  }
  const index = Math.floor(len / 2);
  const indexVal = arr.splice(index, 1)[0];
  const left = [];
  const center = [indexVal]; // 添加等于基准数组
  const right = [];
  for (let d of arr) {
    if (d < indexVal) {
      left.push(d);
    } else if (d === indexVal) {
      center.push(d);
    } else {
      right.push(d);
    }
  }
  return quickSort(left).concat(center).concat(right);
}

归并排序

  • firefox safary Arr.sort()使用归并排序实现
  • 步骤
  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
  4. 重复步骤 3 直到某一指针达到序列尾；
  5. 将另一序列剩下的所有元素直接复制到合并序列尾。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function merge(left, right) {
  //将两个有序的数组合并
  let result = [];
  while (left.length > 0 && right.length > 0) {
    if (left[0] < right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  return result.concat(left).concat(right);
}
function mergeSort(arr) {
  //将数组分开
  if (arr.length == 1) {
    return arr;
  }
  let middle = Math.floor(arr.length / 2),
    left = arr.slice(0, middle),
    right = arr.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}

希尔排序

  • 步骤
  1. 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
  2. 按增量序列个数 k，对序列进行 k 趟排序；
  3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function shellSort(arr) {
  if (arr.length < 2) {
    return arr;
  }
  let n = arr.length;
  let temp;
  for (gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {
    for (i = gap; i < n; ++i) {
      for (j = i - gap; j >= 0 && arr[j + gap] < arr[j]; j -= gap) {
        temp = arr[j];
        arr[j] = arr[j + gap];
        arr[j + gap] = temp;
      }
    }
  }
  return arr;
}

参考